1. Field of the Invention
The present invention generally concerns buffer allocation in processing devices, and in particular concerns allocation of a next available buffer in a microprocessor.
2. Background Information
A common approach in trying to find the next available buffer in a processing device is to implement priority encoders, which determine the next available buffer through use of a pointer to the current buffer and a bit vector representing the combination of available buffers. For each pointer position, a priority encoder determines the next buffer from the available buffer bit vector. For example, if 8 buffers were to be implemented in this manner, 8 priority encoders would typically be used. The output of all the encoders is then driven to a multiplexer (mux), which uses the pointer to the current buffer to pick which encoder's output to use. Each encoder is for a different pointer value, and accordingly, cannot be shared by other pointer values.
The following truth tables correspond to an exemplary 3-buffer configuration that employs priority encoders.
InputOutputEncoder 0:000000001001010010011010100100101100110010111010Encoder 1:000000001001010010011001100100101100110100111100Encoder 2:000000001001010010011001100100101001110010111001Output Mux(Input is current pointer and guaranteed to have oneand only one bit set):001Encoder0010Encoder1100Encoder2
As the number of buffers increase, the number of input and output bits for each encoder also increases. Furthermore, this requires an increase in the size of the mux, as well. As a result, there is an almost exponential growth in the required logic as the number of buffers increase. Accordingly, an improved approach is desired.